package com.ww.springboot.boot.algorithm.leetcode1;

import com.ww.springboot.boot.algorithm.tree.TreeNode;
import com.ww.springboot.boot.algorithm.tree.TwoTreeDemo2;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-04-01 15:56
 */
public class BJ1609奇偶树 {


    public static void main(String[] args) {

        int[] rootArr = {1, 10, 3, 12, 0, 0, 8, 0, 0, 0, 4, 7, 6, 0, 0, 0, 9, 0, 2};

        TreeNode root = new TreeNode();
        TwoTreeDemo2.setValue(root, rootArr);
        System.out.println(root);

        isEvenOddTree(root);
    }


    /**
     * 将偶数下标和奇数下标分别组成新的二叉树 再分别判断是否符合二叉树定义
     *
     * @param root
     * @return
     */
    public static boolean isEvenOddTree(TreeNode root) {

        //使用中序遍历
        List<Integer> listOdd = new ArrayList<>();
        List<Integer> listEven = new ArrayList<>();

        splitTree(root, listOdd, listEven);
        System.out.println(listOdd);
        System.out.println(listEven);
        return true;
    }

    /**
     * 将二叉树拆分
     *
     * @param root
     */
    private static void splitTree(TreeNode<Integer> root, List<Integer> listOdd, List<Integer> listEven) {
        //记录层数
        int floor = 0;
        setValue(floor, root, listOdd, listEven);

    }

    /**
     * 使用多层list分别存储每层元素 判断是否符合递增或递减 奇数或偶数
     * @param floor
     * @param root
     * @param listOdd
     * @param listEven
     */
    private static void setValue(int floor, TreeNode<Integer> root, List<Integer> listOdd, List<Integer> listEven) {
        if (root == null || root.getVal() == null) {
            return;
        }
        setValue(floor + 1, root.getLeft(), listOdd, listEven);
        if (floor % 2 == 0) {
            listEven.add(root.getVal());
        } else {
            listOdd.add(root.getVal());
        }
        setValue(floor + 1, root.getRight(), listOdd, listEven);
    }
}
